//
//  RecoverTree.swift
//  LeetCodeSummary
//
//  Created by 彭西西 on 2020/8/8.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  99. 恢复二叉搜索树

import UIKit

/*
 99. 恢复二叉搜索树

 二叉搜索树中的两个节点被错误地交换。

 请在不改变其结构的情况下，恢复这棵树。

 示例 1:

 输入: [1,3,null,null,2]

    1
   /
  3
   \
    2

 输出: [3,1,null,null,2]

    3
   /
  1
   \
    2
 示例 2:

 输入: [3,1,4,null,null,2]

   3
  / \
 1   4
    /
   2

 输出: [2,1,4,null,null,3]

   2
  / \
 1   4
    /
   3
 进阶:

 使用 O(n) 空间复杂度的解法很容易实现。
 你能想出一个只使用常数空间的解决方案吗？
 */

class RecoverTree: NSObject {
    
    //根据题意，二叉树中只有“两个”节点被错误地交换，我们可以对二叉搜索树进行中序遍历，正常情况下是一个递增数组，题中有两个节点被交换，因此可以直接想到联想到中序遍历的数组大概是什么样的一种情况
    /*
     eg 一个有序数组 1 2 3 4 5 6 7
     假如交换3和6两个元素 则变成了 1 2 6 4 5 3 7，会发现数组中有两处位置不满足升序的排列，即 6>4 和 5>3 两个位置，要恢复序列则需要交换6和3
     或者交换3和4两个相邻的元素    1 2 4 3 5 6 7  此时数组中仅有一处位置不满足升序，即 4>3
     所有情况只能是以上两种，因此我们很容易就能想到解法。
     对给定的数组进行正常的中序遍历，然后从中查找n[i]>n[i+1]位置的个数，
     如果位置个数为1，设索引为a，那么交换 n[a] 和 n[a+1]；
     如果位置个数为2，设索引为a，b 那么交换 n[a] 和 n[b+1] 就能得出结果
    */
    func recoverTree(_ root: TreeNode?) {
        guard root != nil else {
            return
        }
        self.middleOrder(root)
        let arr = self.findNotUpPosition(middleResult)
        //
        self.exchangNode(root, arr[0], arr[1], 2)
    }
    
    var middleResult:Array<Int> = []
    //中序遍历
    func middleOrder(_ root: TreeNode?){
        guard root != nil else {
            return
        }
        self.middleOrder(root?.left)
        middleResult.append(root!.val)
        self.middleOrder(root?.right)
    }
    
    //查找中序遍历结果中不满足升序的位置  最终返回需要交换的两个点
    func findNotUpPosition(_ nums: [Int])->[Int]{
        var notUpPosition:[Int] = []
        var i = 0
        while i < nums.count-1 {
            if nums[i] > nums[i+1] {
                notUpPosition.append(i)
            }
            i += 1
        }
        if notUpPosition.count == 1 {
            notUpPosition.append(nums[notUpPosition[0]+1])
            return [nums[notUpPosition[0]],
                    nums[notUpPosition[0]+1]
            ]
        }else if notUpPosition.count == 2 {
            return [nums[notUpPosition[0]],
                    nums[notUpPosition[1]+1]]
        }
        return []
    }
 
    //对二叉搜索树进行指定位置的交换
    func exchangNode(_ root: TreeNode? , _ num1: Int, _ num2: Int, _ count: Int){
        guard root != nil else {
            return
        }
        if root?.val == num1 || root?.val == num2{
            root?.val = root?.val == num1 ? num2 : num1
            var count = count
            count -= 1
            if count == 0 {
                return
            }
        }
        self.exchangNode(root?.right, num1, num2, count)
        self.exchangNode(root?.left, num1, num2, count)
    }
    
}
